package com.cuz.daileetcode;

import sun.security.jgss.HttpCaller;

import java.util.LinkedList;
import java.util.List;

public class Day55 {


    public static class BracketSequenceGenerate {
        public static void main(String[] args) {
            System.out.println(solution1(3));
            System.out.println(solution2(3));
        }

        public static List<String> solution1(int bracket) {
            List<String> result = new LinkedList<>();
            backtrack(result, new StringBuilder(), 0, 0, bracket);
            return result;
        }

        static void backtrack(List<String> result, StringBuilder sequence, int leftNum, int rightNum, int max) {
            if (leftNum == max && rightNum == max) {
                result.add(sequence.toString());
                return;
            }
            if (leftNum < max) {
                sequence.append('(');
                backtrack(result, sequence, leftNum + 1, rightNum, max);
                sequence.deleteCharAt(sequence.length() - 1);
            }
            if (rightNum < leftNum) {
                sequence.append(')');
                backtrack(result, sequence, leftNum, rightNum + 1, max);
                sequence.deleteCharAt(sequence.length() - 1);
            }
        }

        public static List<String> solution2(int n) {
            List<String> res = new LinkedList<>();
            process(res, new StringBuilder(), n, n);
            return res;
        }

        static void process(List<String> res, StringBuilder temp, int leftSurplus, int rightSurplus) {
            if (leftSurplus == 0 && rightSurplus == 0) {
                res.add(temp.toString());
                return;
            }
            if (rightSurplus == leftSurplus) {
                process(res, new StringBuilder(temp).append('('), leftSurplus - 1, rightSurplus);
            } else if (leftSurplus < rightSurplus) {
                if (leftSurplus > 0) {
                    process(res, new StringBuilder(temp).append('('), leftSurplus - 1, rightSurplus);
                }
                process(res, new StringBuilder(temp).append(')'), leftSurplus, rightSurplus - 1);
            }
        }


    }


    public static class LongestPalindromeSubstring {

        static String solution1(String str) {
            if (str == null || "".equals(str)) {
                return "";
            }
            char[] charArray = str.toCharArray();
            int strLen = charArray.length;
            boolean[][] dp = new boolean[strLen][strLen];
            int max = 1;
            int subStringStart = 0;
            for (int i = 0; i < strLen; i++) {
                dp[i][i] = true;
            }
            for (int curLength = 2; curLength <= strLen; curLength++) {
                for (int start = 0; start < strLen - curLength + 1; start++) {
                    int end = start + curLength - 1;
                    if (end >= strLen) {
                        break;
                    }
                    if (charArray[start] == charArray[end]) {
                        if (end - start <= 2) {
                            dp[start][end] = true;
                        } else {
                            dp[start][end] = dp[start + 1][end - 1];
                        }
                    }
                    if (dp[start][end]) {
                        max = Math.max(max, curLength);
                        subStringStart = start;
                    }
                }
            }
            return str.substring(subStringStart, max + subStringStart);
        }


        class Solution {
            public String longestPalindrome(String s) {
                if (s == null || s.length() < 1) {
                    return "";
                }
                int start = 0, end = 0;
                for (int index = 0; index < s.length(); index++) {
                    //index 作为中心，这个时候 start = index - (len - 1) / 2  end = index + len / 2;
                    int len1 = expandAroundCenter(s, index, index);
                    // index 和 index+1 作为中心 start = index - (len - 2) / 2  end = index + len / 2
                    //但是这个时候 len 是偶数 (len - 2) / 2= (len - 1) / 2
                    int len2 = expandAroundCenter(s, index, index + 1);
                    int len = Math.max(len1, len2);
                    if (len > end - start) {
                        start = index - (len - 1) / 2;
                        end = index + len / 2;
                    }
                }
                return s.substring(start, end + 1);
            }

            public int expandAroundCenter(String s, int left, int right) {
                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                    --left;
                    ++right;
                }
                return right - left - 1;
            }
        }
    }
}
